package com.lijing.RadixSort;

import com.lijing.SelectSort.Selection;
import com.lijing.ShellSort.Shell;
import com.lijing.StopWatch.StopWatch;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class RadixSort {
    public static void main(String[] args) {
        int n = 800000;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int)(Math.random()*n*10);
        }
        StopWatch sw = new StopWatch();
        sort(arr);
        double time = sw.elapsedTime();
        //System.out.println(Arrays.toString(arr));
        System.out.println("Cost time:"+time+"s");
    }
    //桶排序,0-9组成的数字，需要10个桶0-->9，
    private static void sort(int[] arr){
        //首先需要求出arr中最大数字的位数，是即将排序的总次数
        int maxValue = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > maxValue){
                maxValue = arr[i];
            }
        }
        //计算最大数字的最大位数
        int maxLength = (maxValue+"").length();

        //桶，10个桶，每个桶的容量是arr的长度，考虑最坏的情况
        int[][] bucket = new int[10][arr.length];
        //每个桶对应的放置元素个数，bucketElementCnts[0]表示第一个桶的元素个数
        int[] bucketElementCnts = new int[10];

        for (int i = 0; i < maxLength; i++) {
            //①入桶
            //每一轮排序,遍历arr中的每一个元素，放到桶中
            for (int j = 0; j < arr.length; j++) {
                //获取个位、十位、百位......
                int digitOfElement = (int) (arr[j] /Math.pow(10,i) %10);
                //将每个元素放入到对应的桶中
                bucket[digitOfElement][bucketElementCnts[digitOfElement]] = arr[j];
                bucketElementCnts[digitOfElement]++;
            }
            //②出桶
            //遍历所有桶，有元素的就挨个出桶，没有元素的就不做操作
            int index = 0;
            for (int j = 0; j < bucketElementCnts.length; j++) {
                if(bucketElementCnts[j] != 0){//有元素
                    for (int k = 0; k < bucketElementCnts[j]; k++) {
                        arr[index++] = bucket[j][k];
                    }
                }
                //入桶完毕，需要清空bucketElementCnts
                bucketElementCnts[j] = 0;
            }
        }
    }
}
